package ch02Sort;

import java.util.Random;
import java.util.Stack;

//最大堆(优先队列)
public class MaxPQ<Key extends Comparable<Key>> {
    private Key[] pq;
    private int N = 0;  //区间：[1,n]

    public MaxPQ(Key[] pq) {
        this.pq = pq;

    }

    public boolean isEmpty() {
        return  N == 0;
    }
    public int size() {
        return N;
    }
    public void insert(Key v){
        pq[++N] = v;
        swim(N);
    }

    public Key delMax() {
        Key max = pq[1];
        exch(1, N);
        //jvm回收
        pq[N--] = null;
        sink(1);
        return max;

    }
    //下沉
    private void sink(int k){
        while (2 * k <= N) {
            int i = 2 * k;
            if (i<N&&less(i, i + 1)) {
                i++;
            }
            if(!less(k,i)) break;
            exch(i,k);
            k = i;
        }
    }

    //上浮
    private void swim(int k){
        while (k > 1 && less(k / 2, k)) {
            exch(k / 2, k);
            k /= 2;
        }

    }

    public boolean less(int i, int j) {
        return pq[i].compareTo(pq[j])<0;
    }

    public void exch(int i, int j) {
        Key t = pq[i];
        pq[i] = pq[j];
        pq[j] = t;
    }
    //堆排序
    public void sort() {
        //1.构造堆,从非叶节点最右边向左遍历，遍历中使用sink()
        for (int i = N / 2; i >= 1; i--) {
            sink(i);
        }
        //2.顶端元素和低端元素交换位置，N--,再进行sink()
        while (N > 1) {
            exch(1, N);
            N--;
            sink(1);
        }

    }
    public void print(){
        for (Key key : pq) {
            System.out.printf("%d ", key);
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int n = 50;
        Integer[] a = new Integer[51];
        for (int i = 0; i <= 50; i++) {
            a[i] = new Integer(0);
        }
        MaxPQ<Integer> maxPQ = new MaxPQ<Integer>(a);
        for (int i = 0; i < 50; i++) {
            maxPQ.insert(new Random().nextInt()%50+50);
        }

        maxPQ.sort();
        maxPQ.print();
        System.out.println();
    }
}
